﻿// 0904train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;

/*
 提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回0
简单数学表达式只能包含以下内容：0-9数字，符号 +-*
说明：
1. 所有数字，计算结果都不超过long
2. 如果有多个长度一样的，请返回第一个表达式的结果
3. 数学表达式，必须是最长的，合法的
4. 操作符不能连续出现，如 +--+1 是不合法的


示例
输入
1-2abcd
输出
-1
 */
class Solution01
{
public:
    int computed(string&cal_str)
    {
        cal_str = cal_str + ' ';
        int curr_num = 0;
        char pre_char = '+';
        vector<int>stack_v;
        for (int i=0; i<cal_str.size(); i++)
        {
            char curr_ch = cal_str[i];
            if (isdigit(curr_ch))
            {
                curr_num = curr_num * 10 + curr_ch - '0';
                continue;
            }

            //1-2*4
            //遇到符号看前导符号是什么
            if (pre_char=='+')
            {
                stack_v.push_back(curr_num);
            }
            else if (pre_char =='-')
            {
                stack_v.push_back(curr_num*(-1));
            }
            else if (pre_char=='*')
            {
	            //栈里退一个数字进行运算
                int top_num = stack_v.back();
                stack_v.pop_back();
                stack_v.push_back(top_num * curr_num);
            }
            //重置curr_num
            curr_num = 0;
            //重置pre_char
            pre_char = curr_ch;
        }

        int sum = 0;
        for (auto&num:stack_v)
        {
            sum += num;
        }
        return sum;
        //computed
    }

    void solve01(string& origin_str)
    {
        //前后补两个字符，防止越界
        string exec_str = 'a' + origin_str + 'a';
        int s_size = exec_str.size();

        int i = 1;
        while (i < s_size)
        {
            char i_char = exec_str[i];
            if (isdigit(i_char) || i_char == '+' || i_char == '-')
            {
                //j继续向前拓展
                int j = i;
                while (j < s_size)
                {
                    char j_char = exec_str[j];
                    if (isdigit(j_char))
                    {
                        if (j_char != '0')
                        {
                            j++;
                            continue;
                        }

                        if (!isdigit(exec_str[j - 1]) && isdigit(exec_str[j + 1]))
                        {
                            //01,02不合格，只能截到0
                            j++;
                            break;
                        }
                        //如果0合格，那么j继续往前走
                        j++;
                        continue;
                    }
                    else if (j_char == '+' || j_char == '-' || j_char == '*')
                    {
                        //下一个必须是数字
                        if (isdigit(exec_str[j + 1]))
                        {
                            j++;
                            continue;
                        }
                        //否则直接退循环
                        break;
                    }
                    //其他字符直接break
                    break;
                    //while (j<s_size)
                }

                //j的循环走完，根据j的情况，更新i的index
                if (i == j)
                {
                    //防止i死循环
                    i++;
                    continue;
                }

                //找到最长数学表达式，更新result;
                if ((j - i) > (end_index - start_index))
                {
                    start_index = i;
                    end_index = j;
                }
                i = j;
                continue;

                //if (isdigit(i_char) || i_char=='+' || i_char=='-')
            }

            //如果不满足条件，直接跳i
            i++;
            //while (i<s_size)
        }

        //while循环结束，更新计算结果
        if (start_index == end_index)
        {
            //如果没有符合要求的，则返回0
            cout << 0;
            return;
        }

        string cal_str = exec_str.substr(start_index, end_index - start_index);
        cout << computed(cal_str);
    }

    Solution01(string&origin_str)
    {
        solve01(origin_str);
        //Solution01
    }
private:
    //存储最长表达式起始，末尾
    int start_index = -1, end_index = -1;
};

/*
 他打算给孩子买蛋糕和小礼物，蛋糕和小礼物各买一个，他的预算不超过x元
 蛋糕cake和小礼物gift都有多种价位的可供选择
请返回小牛共有多少种购买方案

输入描述
第一行表示cake的单价，以逗号分隔
第二行表示gift的单价，以逗号分隔
第三行表示x预算
输出描述
输出数字表示购买方案的总数

10,20,5
5,5,2
15
输出
6
小牛有6种购买方案，所选蛋糕与所选礼物在数组中对应的下标分别是：
第1种方案: cake [0] + gift [0] = 10 + 5 = 15;
第2种方案: cake [0] + gift [1]= 10 + 5 = 15;
第3种方案: cake [0] + gift [2] = 10 + 2 = 12;
第4种方案: cake [2] + gift [0] = 5 + 5 = 10;
第5种方案: cake [2] + gift [1]= 5 + 5 = 10;
第6种方案: cake [2] + gift [2] = 5 + 2 = 7
 */
class Solution02
{
public:
    Solution02(vector<int>&vec_1, vector<int>&vec_2, int limit)
    {
        sort(vec_1.begin(), vec_1.end());
        sort(vec_2.begin(), vec_2.end());

        int result = 0;
        int i = 0;
        while (i<vec_1.size())
        {
	        if (vec_1[i]<=limit)
	        {
                int j = 0;
                while (j<vec_2.size())
                {
                    int curr = vec_1[i] + vec_2[j];
                    if (curr<=limit)
                    {
                        result += 1;
                        j++;
                    }
                    else
                    {
                        //超过价格
                        break;
                    }
                    //vec_2是否有符合要求的
                    //while (j<vec_2.size())
                }
                i++;
	        }
            else
            {
                break;
            }
        }

        cout << result;
        //Solution02
    }
};


/*
给定一个整数数组nums，请你在该数组中找出两个数，
使得这两个数的和的绝对值abs(nums[x] + nums[y])为最小值
并按从小到大返回这两个数以及它们和的绝对值。每种输入只会对应一个答案
数组中同一个元素不能使用两遍

输入
一个通过空格分割的整数序列字符串，最多1000个整数，且整数数值范围是[-65535,65535]
输出
两个数以及两数之和绝对值

输入
-1 -3 7 5 11 15
输出
-3 5 2

因为abs(nums[0]+nums[2]) = abs(-3+5) = 2在所有数对中最小，所以返回-3 5 2
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec)
    {
        sort(num_vec.begin(), num_vec.end());
        int min_abs_sum = INT_MAX;
        vector<int>result_vec;
        for (int i=0; i<num_vec.size(); i++)
        {
			for (int j=num_vec.size()-1; j>=i+1; j--)
			{
				if (abs(num_vec[i] + num_vec[j] )<min_abs_sum)
				{
                    min_abs_sum = abs(num_vec[i] + num_vec[j]);
                    result_vec.clear();
                    result_vec.push_back(num_vec[i]);
                    result_vec.push_back(num_vec[j]);
				}
			}
        }

        sort(result_vec.begin(), result_vec.end());

        cout << result_vec[0] << ' ' << result_vec[1] << ' ';
        cout << min_abs_sum;

       //Solution03
    }
};

int main()
{
	//{
 //       int num1 = -1, num2 = -3;
 //       cout << num1 + num2;
 //       return 0;
	//}
	{
        //-1 -3 7 5 11 15
        vector<int>num_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
/*
10,20,5
5,5,2
15
*/
        vector<int>vec_1, vec_2;
        string input;
        getline(cin, input);
        stringstream oh_sstream1(input);
        string token;

        while (getline(oh_sstream1, token, ','))
        {
            vec_1.push_back(stoi(token));
        }

        getline(cin, input);
        stringstream oh_sstream2(input);
        while (getline(oh_sstream2, token, ','))
        {
            vec_2.push_back(stoi(token));
        }

        int limit;
        cin >> limit;

        Solution02 solu(vec_1, vec_2, limit);

        return 0;
	}
    string origin_str = "-0200";
    Solution01 solu(origin_str);

    //string test_cal = "1-2*4";
    //cout << solu.computed(test_cal);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
